'''
Company: TWL
Author: xue jian
Email: xuejian@kanzhun.com
Date: 2020-11-13 09:34:21
'''
#
# @lc app=leetcode.cn id=328 lang=python3
#
# [328] 奇偶链表
#

# @lc code=start
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        odd = head
        if not head:
            return head
        even = head.next
        oddptr = odd
        evenptr = even
        while oddptr and evenptr:
            oddptr.next = evenptr.next
            oddptr = oddptr.next
            if not oddptr:
                break
            evenptr.next = oddptr.next
            evenptr = evenptr.next
        while odd.next:
            odd = odd.next
        odd.next = even
        return head
        
# @lc code=end

if __name__ == "__main__":
    solution = Solution()
    tmp = [1, 2, 3, 4, 5, 6, 7]
    head = ListNode(tmp[0])
    tmpptr = head
    for i in range(1, len(tmp)):
        tmpp = ListNode(tmp[i])
        tmpptr.next = tmpp
        tmpptr = tmpptr.next

    head = solution.oddEvenList(head)
    ans = []
    while head:
        ans.append(head.val)
        head = head.next
    print(ans)